#include<iostream>
#include<random>
#include<algorithm>
#include<ctime>

using namespace std;

class BubbleSort
{
	public:
		static void swap(int *arr,int i,int j){	//交换函数
			int temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
		}
		static void bubblesort(int *arr, int length){	//冒泡升序排序
			if(!arr||length<2)
				return;
			bool orderly;
			for(int end=length-1;end!=0;end--){
				orderly = true;		//假设初始有序
				for(int i=0;i<end;i++){
					if(arr[i]>arr[i+1]){
						swap(arr,i,i+1);
						orderly = false;	//发生了交换，证明序列无序
					}
				}
				if(orderly)
					break;		//说明已经全部有序，结束循环，避免最坏情况的发生
			}
		}

//		static void rightsort(int []arr,const int& length);
		static int* generateRandomArray(int size,int value,int &len){
			static default_random_engine e;
			e.seed(time(0));
			static uniform_real_distribution<double>u(0,1);
			//cout<<(int)(u(e)*size)<<endl;
			int ss = (int)((size+1)*u(e));
			//cout<<ss<<endl;
			int *arr = new int[ss];
			len = ss;
			for(size_t i=0;i<ss;i++){
				arr[i] = (int)((value+1)*u(e))-(int)(value*u(e));
				cout<<arr[i]<<" ";
			}
			cout<<endl;
			return arr;
		}
		static void printArray(int *arr,int len){
			for(size_t i=0;i<len;i++){
				cout<<arr[i]<<" ";
			}
			cout<<endl;
		}
		
};

int main()
{
	int size = 100;
	int value = 100;
	int len = 0;
	int *arr1 = BubbleSort::generateRandomArray(size,value,len);
	BubbleSort::printArray(arr1,len);
	BubbleSort::bubblesort(arr1,len);
	BubbleSort::printArray(arr1,len);

	return 0;
}
